package algorithms;

public class MergeSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MergeSort merge = new MergeSort() ;
		int[] arr = new int[]{3,5,8,9,10,6,7,13,2,1} ;
		int[] all = merge.mergeSort(arr,0,arr.length-1) ;
		System.out.println(all.length);
		for (int i = 0; i < all.length; i++) {
			System.out.print(all[i]+" ");
		}
	}
	
	public int[] mergeSort(int[] arr,int p,int r){
		if(r-p==0){
			int[] tmp = new int[r-p+1] ;
			tmp[0]=arr[p] ; 
			return tmp ;
		}else{
			int q = (p+r) /2 ;
			int left[] = mergeSort(arr, p ,q) ;
			int right[] = mergeSort(arr, q+1 ,r) ;
			return mergerCombina(left, right) ;
		}
	}
	
	public int[] mergerCombina(int[] left,int[] right){
		int[] tmp = new int[left.length+right.length];
		int i=0,j =0  ;
		for (int index = 0 ,max=tmp.length; index < max;index++) {
			if(j==left.length){
				tmp[index]=right[i++] ;
				continue ;
			}else if(i==right.length){
				tmp[index]=left[j++] ;
				continue ;
			}
			
			if(left[j]>=right[i]){
				tmp[index] = right[i++] ;
				
			}else {
				tmp[index] = left[j++] ;
			}
		}
		
		
		return tmp ;
	}

}
